import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Text {
    List<String> ret = new ArrayList<>();
    public void permutationHelper(char[] vals,int[] used,String str) {
        if(str.length() == vals.length) {
            ret.add(str);
            return;
        }
        for(int i = 0;i < vals.length;i++) {
            if(i>0 && vals[i] == vals[i-1] && used[i-1] == 0 || used[i] == 1) {
                continue;
            }
            used[i] = 1;
            str = str + vals[i]+"";
            permutationHelper(vals,used,str);
            used[i] = 0;
            str = str.substring(0,str.length()-1);
        }
    }
    public String[] permutation(String s) {
        char[] vals = new char[s.length()];
        for (int i = 0; i < vals.length; i++) {
            vals[i] = s.charAt(i);
        }
        Arrays.sort(vals);
        int[] used = new int[s.length()];
        String str = "";
        permutationHelper(vals,used,str);
        String[] array = new String[ret.size()];
        int i = 0;
        for(String string : ret) {
            array[i] = string;
            i++;
        }
        return array;
    }
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ret1 = new ArrayList<>();
    public void pathSumHelper(TreeNode root,int targetSum) {
        if(root == null) {
            return;
        }
        targetSum -= root.val;
        path.add(root.val);
        if(0 == targetSum && root.left == null &&root.right == null) {
            ret1.add(new ArrayList<>(path));
        }
        pathSumHelper(root.left,targetSum);
        pathSumHelper(root.right,targetSum);
        path.remove(path.size()-1);
    }
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return ret1;
        }
        pathSumHelper(root,targetSum);
        return ret1;
    }
}
